\documentclass[a4paper]{article}

% Document properties
\date{\today}
\title{Compiler Construction\\peephole optimizer for SimpleScalar DLX assembly code}
\author
{
  Butrus, Eenass\\
  Liberatore, Lorenzo\\
  Martoidjojo, Gail
}

% Front page without page number and table of contents
\begin{document}
\maketitle
\thispagestyle{empty}
\pagebreak
\tableofcontents
\pagebreak

\section{Problem description}

In this project we had to develop a peephole optimizer for SimpleScalar DLX assembly code.
This peephole optimizer has to read assembly code generated by a xgcc cross compiler and 
optimize this code generating an assembly output file in which redundant instructions has
been removed without destroing the original functionality and output of the code obtained
by running the optimized assembly.

\section{Peephole optimizations}

A Peephole optimizer differs from other types of optimization in the fact that 
it execute on small parts of the code (the so called basic blocks). Basic blocks are 
literally parts of assembly code defined by a label or a jump or a branch or subroutines that 
permits us to divide the code in many logically separated pieces that will allow us to work on the
optimizations problems locally using an approach called "divide en conquer" method, and from that
small blocks optimizations obtain a global optimization that allow us in the end to optimize it entirely.

\section{Using the optimizer}

To optimize with our's Peephole optimizer the Assembly code generated by the machine the command you have
to use to do it is:

\begin{verbatim}
python symple_peephole_optimizer.py
\end{verbatim}

Prerequisites for running this program having python installed on your machine. Python, if not already
installed, can be downloaded from {\tt www.python.org}. Python version 2.7 is recommended.

\section{Implementation}

\subsection{Used tools}

In the first period of this project we were really confused on which programming language we should use
to give birth to this project, after a deep analysis of feasibility study of our group skills and the
amount of time we had to finish it we came to the conlusion that our's optimal solution to do it,
could be only using Python language.
This language even if not known from all the memembers of the group in the beginning has an incredibly fast learning
curve that allowed us to start optimizing almost immediatly thanks to its flexibility, portability and simplicity.
This allowed us also to focus more on the optimizations instead of loosing time on the "how to do it" part.

\subsection{Group Management}

To complete our project we split the work in subproblems such as parts of the code to be written individually
,the test phase of the benchmarks and also to write this document. We all wrote the different parts.
Since this project was done by three persons the things to do has been splitted in three, in this way we could do it
faster.
For all this phases, of course, in the end has been predicted another phase that would help us to stick toghether 
all the separated parts creating in the end one big project.

\subsection{Project Realization}

The persons in our group came from different backgrounds and different universities so we choosed to use internet
as a tool to create our project, since in most cases our "free time" to do this project does not match at all.
So all the work basically has been done at home, by email or using a repository online and on the labs or when we
were more free we met each other to test it or to talk about this.

\section{Peephole optimizator parts}

In this section we will explain how the part of the code of our Peephole optimizer has been built,so we
will write in detail all the parts of the code and their meaning.

\subsection{Assembly instructions recognizement}

The first things to start with was the Assembly instruction recognizement by the Python code. We thought at this 
really carefully and we came to the conclusion that the best methods to do it was to use the powerful Phyton code 
strings management.
Thanks to this we have built up the function ``read\_file(filename)" that reads the file and split its contents in to two parts: compiler directives which are the first lines of the assembly code till the keyword ``.ent", after this keyword begin the code of the program; this code is saved in another list.

\subsection{Remove redundant branches}
After reading the assembly code, we will look at specifiek cases of branches, jumps and labels and remove the redundant one. Therefore, a funcction called ``remove\_redundant\_branches" is built and it is applied only for the assembly code without the compiler directives. In this function we look for four cases: the first one is ``jL1" followed directly with ``L1", in this situation the jump would be removed. The second one checks the accurance labels in sequence, in this case one of the labels will be kept and the labels of all the branches and jumps to the removeed labels will be replaced with the one that is kept. The third one is the accurance of ``beq" followed by ``j", in this case ``bne" will be replaced bij ``bne" and the lable will be that one of the ``j", then the jump will be removed. The last one is the case that a label contains only one instruction and that instruction is ``j", here the label will be removed and all the jumps to this label will be replaced with that one of the jump.

\subsection{The basic blocks}
After removing redundant branches, jumps and labels, the code will be devided into basic blocks. The basic blocks consist of a number of instructions that are excuted sequentially and they can be recognized through the leaders.These laeders are the first statement followed the compiler directives, any statement that is a target of the jump  (a label) and any statement that followes a branch or a jump. This is done by the function ``make\_blocks".
\subsection{Local Optimization on Basic Blocks}

This part as the title said talks about all the optimizations that has been made to optimize the code locally on the basics blocks.




\subsubsection{peephole_optimizer}
This is the main function that permits optimizations in the code using all the functions described before.


\section{Results}

\section{Future improvements}

\section{Conclusion}

\section{References}

\end{document}
